public class 数组问题 {
    //最小未出现正数,原地hash
    public static int firstMissingPositive(int[] nums) {
        int m = nums.length;
        for (int i = 0; i < m; i++) {
            if (nums[i] < 0)
                nums[i] = 0;
        }
        for (int i = 0; i < m; i++) {
            int temp = nums[i];
            if (nums[i] != -1)
                nums[i] = 0;
            while (temp <= m && temp > 0) {
                int t = nums[temp - 1];
                nums[temp - 1] = -1;
                temp = t;
            }
        }
        for (int i = 0; i < m; i++) {
            if (nums[i] == 0)
                return i + 1;
        }
        return m + 1;
    }

    public static int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        if (nums[0] == target)
            return 0;
        while (r > l) {
            int mid = (l + r) / 2;
            if (nums[mid] > target) {
                if (nums[l] > 1)
                    r = mid - 1;
            } else if (nums[mid] == target)
                return mid;
            else l = mid + 1;
        }

        return r;
    }

    //最大子数组
    public static int maxSubArray(int[] nums) {
        int sum = nums[0];
        int last = sum;
        for (int i = 1; i < nums.length; i++) {
            if (sum < 0)
                sum = nums[i];
            else sum += nums[i];
            last = Math.max(sum, last);
        }
        System.out.println(sum);
        return sum;
    }

    public static boolean canJump(int[] nums) {
        int m = nums.length;
        boolean res[] = new boolean[m];
        res[m - 1] = true;
        for (int i = m - 2; i >= 0; i--) {
            int n = nums[i];
            for (int j = i+1; j <= n + i && j < m; j++) {
                if (res[j]) {
                    res[i] = true;
                    break;
                }
            }
        }
        for(int i=0;i<m;i++)
            System.out.print(nums[i]+"  ");
        System.out.println();
        for(int i=0;i<m;i++)
            System.out.print(res[i]+"  ");
        return res[0];
    }

    public static void main(String[] args) {
//        firstMissingPositive(new int[]{4, 5, 6, 7, 0, 1, 2});
//        System.out.println(firstMissingPositive(new int[]{5, 6,3, 4,7, 2,1,0, 2}));
//        maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
        canJump(new int[]{0});
    }
}
